package com.zhangxiaofanfan.hotcode.fourth.third;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/n-queens/?envType=study-plan-v2&envId=top-100-liked">51. N 皇后</a>
 *
 * @date 2024-06-29 10:13:57
 * @author zhangxiaofanfan
 */
public class HotCode061 {
    public static void main(String[] args) {
        HotCode061 hotCode = new HotCode061();
        System.out.println(hotCode.partition("abcdd"));
    }

    private List<List<String>> ret = new ArrayList<>();
    public List<List<String>> partition(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            Arrays.fill(dp[i], true);
        }
        for (int rowIndex = s.length() - 1, colIndex; rowIndex >= 0; rowIndex--) {
            for (colIndex = rowIndex + 1; colIndex < s.length(); colIndex++) {
                dp[rowIndex][colIndex] = dp[rowIndex + 1][colIndex - 1] && (s.charAt(rowIndex) == s.charAt(colIndex));
            }
        }
        dfs(s, 0, new ArrayList<>(), dp);
        return ret;
    }

    public void dfs(String s, int i, List<String> curList, boolean[][] dp) {
        if (i >= s.length()) {
            ret.add(new ArrayList<>(curList));
        }
        for (int j = i; j < s.length(); j++) {
            if (dp[i][j]) {
                curList.add(s.substring(i, j + 1));
                dfs(s, j + 1, curList, dp);
                curList.removeLast();
            }
        }
    }
}
